#include <iostream>
#include <chrono>  
#include <cmath>   
 
using namespace std;       
using namespace std::chrono;   
 
// 判断一个数是否为素数
bool isPrime(int num) { 
    if (num <= 1) {
        return false;
    } 

    for (int i = 2; i <= sqrt(num); i++) {
        if (num % i == 0) {
            return false;
        }
    }

    return true;
}

// 逐个判断法求素数个数
int countPrimesByIteration(int n) {
    int count = 0;
    for (int i = 2; i <= n; i++) {
        if (isPrime(i)) {
            count++;
        }
    }
    return count;
}

// 埃氏筛法求素数个数
int countPrimesBySieve(int n) {
    bool *isComposite = new bool[n+1];
    for (int i = 2; i <= n; i++) {
        isComposite[i] = false;
    }

    int count = 0;
    for (int i = 2; i <= n; i++) {
        if (!isComposite[i]) {
            count++;
            for (int j = i * i; j <= n; j += i) {
                isComposite[j] = true;
            }
        }
    }
 
    delete[] isComposite;
    return count;
}

int main() {
    int n;
    cout << "请输入一个正整数n：";
    cin >> n;

    // 逐个判断法求素数个数
    auto start = high_resolution_clock::now();
    int count1 = countPrimesByIteration(n);
    auto stop = high_resolution_clock::now();
    auto duration1 = duration_cast<milliseconds>(stop - start);

    // 埃氏筛法求素数个数
    start = high_resolution_clock::now();
    int count2 = countPrimesBySieve(n);
    stop = high_resolution_clock::now();
    auto duration2 = duration_cast<milliseconds>(stop - start);

    cout << "逐个判断法求素数个数：" << count1 << endl;
    cout << "逐个判断法求解时间：" << duration1.count() << " 毫秒" << endl;
    cout << "埃氏筛法求素数个数：" << count2 << endl;
    cout << "埃氏筛法求解时间：" << duration2.count() << " 毫秒" << endl;

    return 0;
}